#include <vector>
#include <string>
#include <map>


using namespace std;


/*

digits = "23"
["ad","ae","af","bd","be","bf","cd","ce","cf"]

digits = ""
[]

digits = "2"
["a","b","c"]

*/




class Solution {
public:
	map<char, string> mm = {
		{'2',"abc"},{'3',"def"},
		{'4',"ghi"},{'5',"jkl"},
		{'6',"mno"},{'7',"pqrs"},
		{'8',"tuv"},{'9',"wxyz"}
	};
	vector<string> ans;
	string s;
	void dfs(const string& digits, int idx) {
		if (idx >= digits.size()) {
			ans.push_back(s);
			return;
		}

		string letters = mm[digits[idx]];
		for (int i = 0; i < letters.size(); i++) {
			s.push_back(letters[i]);
			dfs(digits,idx + 1);
			s.pop_back();
		}

	}

	vector<string> letterCombinations(string digits) {
		if (digits.empty()) return ans;
		dfs(digits, 0);

		return ans;
	}
};



//
//int main() {
//	Solution s;
//	s.letterCombinations("23");
//	return 0;
//}